package org.example.struct.array2;

import java.util.Arrays;

/**
 * @author liyishan
 * @date 2024/9/12 10:21
 * @apiNote
 */

public class Test02576MaxNumOfMarkedIndices {

    public int maxNumOfMarkedIndices1(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int m = n / 2;
        int res = 0;
        for (int i = 0, j = m; i < m && j < n; i++) {
            while (j < n && 2 * nums[i] > nums[j]) {
                j++;
            }
            if (j < n) {
                res += 2;
                j++;
            }
        }
        return res;
    }

    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int l = 0, r = n / 2;
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (check(nums, m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l * 2;
    }

    public boolean check(int[] nums, int m) {
        int n = nums.length;
        for (int i = 0; i < m; i++) {
            if (nums[i] * 2 > nums[n - m + i]) {
                return false;
            }
        }
        return true;
    }
}
